1. Field of the Invention
The present invention relates to a data retrieval device operating at a high speed with a low power consumption.
2. Description of the Related Art
Along with a development of the Internet, there has been a demand for retrieving and comparing rule data determined in advance with packet data at a high speed for attaining high speed path retrieving and securing of security of a packet. Due to the demand, a content addressable memory (CAM) capable of retrieving data at a high speed has become an essential device (refer to, for example, the Japanese Unexamined Patent Publication No. 2001-236790).
The Japanese Unexamined Patent Publication (Kokai) No. 2001-236790 discloses a content addressable memory having a plurality of physical banks storing different data in accordance with kinds of CAMs, such as a binary CAM having data of only “0” and “1” and a ternary CAM having “X (don't care)” data in addition to the binary data, and a difference of bit lengths.
A currently prevailing CAM is called a ternary CAM wherein one data is composed of a plurality of bit data and each bit can store three kinds, “0”, “1” and “* (don't care)”. The stored data (rule data) and retrieval data (packet data) input from the outside are compared by every bit. When a bit in the stored data is “0 (or 1)” and a corresponding bit of the retrieval data is “0 (or 1)”, the comparison result is matched, while when the retrieval data is “1 (or 0)”, the result is not matched. The “* (don't care)” matches with both “0” and “1” of the retrieval data. This comparison is made on all bits composing the data, and the stored data and the retrieval data are considered to be matched only when all of the data was matched.
Also, since there is a case where the data stored in the CAM and the retrieval data from the outside match more than one, there is a priority circuit for outputting in an ascending (descending) order of the stored address. Normally, it is configured to output only data having the smallest address among the matched data. Accordingly, when creating rule data, significant rule data is stored in an ascending order of the address. An example thereof is shown in FIG. 2.
In FIG. 2, for simplification, stored rule data 100 is largely divided to three 4-bit data regions (A, B and C), and each rule data is stored at a position of a stored address 101 in accordance with the priority order of the rule data (in the figure, a priority tag 102 indicating the order is added to facilitate understanding, but it does not actually exist). Also, a mark “* (4 bits are expressed by one mark in the figure)” in the stored rule data 100 indicates that the value can be any. Furthermore, for example, “2–4” indicates that the data expressing a region from “2” to “4”. In actuality, for specifying such a range, values of respective bits of the stored rule data 100 are made to be suitable values and one rule is expressed by a plurality of stored rule data 100 in some cases; but this time, for simplification, it is assumed that one rule can be expressed by one stored rule data 100.
However, a content addressable memory of the related art is configured to have a comparison circuit for every stored data stored therein and compares retrieval data from the outside with all stored data at a time. Therefore, extremely high-speed retrieving becomes possible, but since all comparison circuits operate at a time, an extremely large power is necessarily consumed. Naturally, a data transmission apparatus using the device becomes capable of transferring data at a high speed, but the large power consumption is a disadvantage. The above Japanese Unexamined Patent Publication No. 2001-236790 does not mention such comparison circuits, and it is considered that it applies a general configuration provided that it is not specifically mentioned, the same disadvantage is shared thereby.
For example, the CAM shown in FIG. 2 can store the rule data effectively and retrieve the data from the outside at an extremely high speed, but the power consumption is extremely large. This is because of comparing all the stored rule data with the retrieval data at a time. Furthermore, it is because of the characteristics of the priority circuit of the CAM that the more significant rule is stored at a position with the smaller (or the larger) address, and it is difficult to specify an area wherein a rule matching with retrieval data from the outside exists in advance. Therefore, it is required to perform a matching comparison on all rule data, so that a large power is consumed for performing the matching comparison.
The disadvantage to be solved in the present invention is the fact that a power consumption is large because of comparing the retrieval data from the outside with the all stored data, and this hinders realization of a large scale data retrieval device at a high speed.